home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 13176 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.7 KB  |  75 lines
  1. Newsgroups: comp.lang.misc,comp.lang.c,gnu.gcc
  2. Path: news.ifm.liu.se!liuida!ricwe
  3. From: ricwe@ida.liu.se (Rickard Westman)
  4. Subject: C compilers which optimize tail calls (was: GOTO controversy)
  5. X-Nntp-Posting-Host: sen21.ida.liu.se
  6. Message-ID: <DpCv8o.9Mw@ida.liu.se>
  7. Sender: news@ida.liu.se
  8. Organization: CIS Dept, Univ of Linkoping, Sweden
  9. References: <314FB5F5.259B@simi.is> <AD87DB279668D9F74@mcdiala15.it.luc.edu> <828549619snz@genesis.demon.co.uk> <oun34tm3c7.fsf@lynx.cs.byu.edu>
  10. Date: Thu, 4 Apr 1996 20:50:47 GMT
  11.  
  12. In article <oun34tm3c7.fsf@lynx.cs.byu.edu>,
  13. Kelly Hall <hall@cs.byu.edu> wrote:
  14. >>>>>> "Lawrence" == Lawrence Kirby <fred@genesis.demon.co.uk> writes:
  15. >    Lawrence> An O(log N) stack depth is generally not a problem. I
  16. >    Lawrence> guess you could say that is finite because there are
  17. >    Lawrence> typically practical upper bounds to N.
  18. >
  19. >Tail recursion is implemented by all non-stupid compilers the same way
  20. >as the imperative (goto) version.  Gcc will do this, whether or not
  21. >your favorite compiler will is a different matter.
  22. >
  23. >No stack problems at all.
  24.  
  25. I have seen several people claim that GCC does proper optimization
  26. of tail calls, but also claims to the contrary.  I decided to test
  27. it for myself with this little tail recursive program:
  28.  
  29.   #include <stdlib.h>
  30.   #include <stdio.h>
  31.   
  32.   int evenp(long i)
  33.   {
  34.     if (i==0) return 1;
  35.     return oddp(i-1);
  36.   }
  37.   
  38.   int oddp(long i)
  39.   {
  40.     if (i==0) return 0;
  41.     return evenp(i-1);
  42.   }
  43.   
  44.   int main(int argc, const char *argv[])
  45.   {
  46.     if (argc!=2) 
  47.       puts("Usage: oddp <number>");
  48.     else if (oddp(abs(atol(argv[1]))))
  49.       puts("Number is odd.");
  50.     else
  51.       puts("Number is not odd.");
  52.     return 0;
  53.   }
  54.  
  55. The sad truth is that this program, compiled with GCC 2.7.0 (-O3),
  56. blows the stack when tested with a number large enough.  Tail calls
  57. within a single function seems to be optimized, though, but this
  58. limitation is really too restrictive for people who want to program
  59. in a functional style (or translate functional programs to C).
  60.  
  61. On the other hand, Suns unbundled C compiler (v3.0.1) seems to
  62. handle this example well, as well as mutual recursion between
  63. different compilation units.  The DEC OSF/1 compiler (v3.11 on an
  64. Alpha) also does OK, but only within a single compilation unit.
  65. More data points?
  66.  
  67. All in all, I don't think it's wise to assume that tail call
  68. optimization is done by the typical C compiler.
  69.  
  70. --
  71. Rickard Westman                   |   "Beware of the panacea peddlers:
  72. Dept. of Computer Science         |    Just because you wind up naked 
  73. Link÷ping University              |    doesn't make you an emperor."  
  74. Sweden                            |              - Michael A Padlipsky
  75.